package com.sheng.leetcode.year2024.month04.day02;

import org.junit.Test;

import java.util.ArrayList;
import java.util.List;

/**
 * @author by ls
 * @date 2024/4/18
 * <p>
 * 894. 所有可能的真二叉树<p>
 * <p>
 * 给你一个整数 n ，请你找出所有可能含 n 个节点的 真二叉树 ，并以列表形式返回。答案中每棵树的每个节点都必须符合 Node.val == 0 。<p>
 * 答案的每个元素都是一棵真二叉树的根节点。你可以按 任意顺序 返回最终的真二叉树列表。<p>
 * 真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点。<p>
 * <p>
 * 示例 1：<p>
 * 输入：n = 7<p>
 * 输出：[[0,0,0,null,null,0,0,null,null,0,0],[0,0,0,null,null,0,0,0,0],[0,0,0,0,0,0,0],[0,0,0,0,0,null,null,null,null,0,0],[0,0,0,0,0,null,null,0,0]]<p>
 * <p>
 * 示例 2：<p>
 * 输入：n = 3<p>
 * 输出：[[0,0,0]]<p>
 * <p>
 * 提示：<p>
 * 1 <= n <= 20<p>
 */
public class LeetCode0894 {

    @Test
    public void test01() {
//        int n = 7;
        int n = 3;
        System.out.println(new Solution().allPossibleFBT(n));
    }
}

class Solution {
    public List<TreeNode> allPossibleFBT(int n) {
        // 真二叉树 是一类二叉树，树中每个节点恰好有 0 或 2 个子节点
        // 左右节点也要求是直二叉树，可以拆分为 左右节点中直二叉树的乘积之和
        List<TreeNode> res = new ArrayList<>();
        if (n == 1) {
            TreeNode root = new TreeNode(0);
            res.add(root);
            return res;
        }
        // 递归解决，类似拆分 7 -> 1,1,5
        for (int i = 1; i < n; i += 2) {
            List<TreeNode> left = allPossibleFBT(i);
            List<TreeNode> right = allPossibleFBT(n - 1 - i);
            for (TreeNode l : left) {
                for (TreeNode r : right) {
                    TreeNode root = new TreeNode(0);
                    root.left = l;
                    root.right = r;
                    res.add(root);
                }
            }
        }
        return res;
    }
}

// Definition for a binary tree node.
class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}
